#include <bits/stdc++.h>
using namespace std;

/*
2311. 小于等于 K 的最长二进制子序列
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个二进制字符串 s 和一个正整数 k 。

请你返回 s 的 最长 子序列的长度，且该子序列对应的 二进制 数字小于等于 k 。

注意：

子序列可以有 前导 0 。
空字符串视为 0 。
子序列 是指从一个字符串中删除零个或者多个字符后，不改变顺序得到的剩余字符序列。
 

示例 1：

输入：s = "1001010", k = 5
输出：5
解释：s 中小于等于 5 的最长子序列是 "00010" ，对应的十进制数字是 2 。
注意 "00100" 和 "00101" 也是可行的最长子序列，十进制分别对应 4 和 5 。
最长子序列的长度为 5 ，所以返回 5 。
示例 2：

输入：s = "00101001", k = 1
输出：6
解释："000001" 是 s 中小于等于 1 的最长子序列，对应的十进制数字是 1 。
最长子序列的长度为 6 ，所以返回 6 。
 

提示：

1 <= s.length <= 1000
s[i] 要么是 '0' ，要么是 '1' 。
1 <= k <= 109
*/

// 法一
class Solution {
public:
    int longestSubsequence(string s, int k) {
        int n = s.size();
        int zeros = count(s.begin(), s.end(), '0'); // 统计0的数量
        int ones = 0;
        long long val = 0;  // 当前子序列的二进制值

        // 二进制位数
        int max_bit = log2(k) + 1;

        // 右到左遍历 选择1  优先处理低位
        for (int i = n - 1; i >= 0; i--) {
            if (s[i] == '0')    continue;  // 0 字符串就直接保留
            else {
                // 2 ^ 30 > 1e9  溢出处理
                // 当前 1 的二进制位置
                int bit_pos = s.size() - 1 - i;
                if (bit_pos >= max_bit)     continue;   // 超过k位的直接丢弃
                if (val + (1LL << bit_pos) <= k) {
                    val += (1LL << bit_pos);     // 添加1的贡献
                    ones++;  // 保留该1
                }  
            }
        }
        return zeros + ones;
    }
};

// 法二
class Solution {
public:
    int longestSubsequence(string s, int k) {
        // 计算k的二进制位数（不含前导零）
        int bitcnt = getBitCount(k);
        int n = s.size();
        
        // 如果k的二进制位数超过字符串长度，整个字符串都可以作为子序列
        if (bitcnt > n) return n;
        
        // 检查最后bitcnt位构成的数值是否<=k
        int cur = 0;
        for (int i = n - bitcnt; i < n; i++) {
            cur = cur * 2 + (s[i] - '0');
            // 防止数值溢出（虽然题目约束k<=1e9，但bitcnt最多30位）
            if (cur > k) break;
        }
        
        // 情况1：最后bitcnt位数值<=k，可以全部保留
        if (cur <= k) {
            // 保留所有前导零（前n-bitcnt个字符中的零）和最后bitcnt位
            return count(s.begin(), s.end() - bitcnt, '0') + bitcnt;
        }
        // 情况2：最后bitcnt位数值>k，只能保留bitcnt-1位
        else {
            // 保留所有前导零和最后bitcnt-1位（舍弃最高位的1）
            return count(s.begin(), s.end() - bitcnt + 1, '0') + bitcnt - 1;
        }
    }

private:
    // 辅助函数：计算整数k的二进制位数
    int getBitCount(int k) {
        if (k == 0) return 1; // 处理k=0的特殊情况
        int cnt = 0;
        while (k) {
            cnt++;
            k >>= 1; // 等价于k /= 2，但位运算效率更高
        }
        return cnt;
    }
};